package com.lw.leetcode.topology.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 1462. 课程表 IV
 *
 * @author liw
 * @version 1.0
 * @date 2021/7/15 14:45
 */
public class CheckIfPrerequisite {

    public static void main(String[] args) {
        CheckIfPrerequisite test = new CheckIfPrerequisite();

        // 输入：n = 2, prerequisites = {{1,0}}, queries = {{0,1},{1,0}}
        //输出：{false,true}
//        int k = 2; int[][] arr = {{1,0}}; int[][] queries = {{0,1},{1,0}};

        //输入：n = 2, prerequisites = {}, queries = {{1,0},{0,1}}
        //输出：{false,false}
//        int k = 2; int[][] arr = {}; int[][] queries = {{0,1},{1,0}};

        // 输入：n = 3, prerequisites = {{1,2},{1,0},{2,0}}, queries = {{1,0},{1,2}}
        //输出：{true,true}
//        int k = 2; int[][] arr = {{1,2},{1,0},{2,0}}; int[][] queries = {{1,0},{1,2}};
        //
        //输入：n = 3, prerequisites = {{1,0},{2,0}}, queries = {{0,1},{2,0}}
        //输出：{false,true}
//        int k = 2; int[][] arr = {{1,0},{2,0}}; int[][] queries = {{0,1},{2,0}};
        //
//        输入：n = 5, prerequisites = {{0,1},{1,2},{2,3},{3,4}}, queries = {{0,4},{4,0},{1,3},{3,0}}
        //输出：{true,false,true,false}
        int k = 2; int[][] arr = {{0,1},{1,2},{2,3},{3,4}}; int[][] queries = {{0,4},{4,0},{1,3},{3,0}};




//        int k = 2; int[][] arr = {{4,8},{4,1},{4,16},{4,3},{4,18},{4,9},{4,2},{4,19},{4,20},{4,13},{4,0},{4,5},{4,22},{4,11},{4,15},{4,21},{8,23},{8,1},{8,16},{8,14},{8,3},{8,7},{8,18},{8,9},{8,2},{8,10},{8,20},{8,0},{8,6},{8,17},{8,22},{8,21},{12,23},{12,1},{12,16},{12,14},{12,7},{12,18},{12,9},{12,19},{12,10},{12,20},{12,0},{12,5},{12,11},{12,15},{12,21},{23,1},{23,16},{23,14},{23,3},{23,7},{23,18},{23,9},{23,2},{23,19},{23,20},{23,13},{23,17},{23,22},{23,15},{23,21},{1,14},{1,3},{1,7},{1,18},{1,9},{1,2},{1,19},{1,13},{1,6},{1,17},{1,15},{1,21},{16,14},{16,19},{16,10},{16,13},{16,0},{16,6},{16,17},{16,11},{14,3},{14,7},{14,18},{14,9},{14,10},{14,20},{14,6},{14,22},{14,11},{14,15},{3,7},{3,18},{3,9},{3,2},{3,19},{3,10},{3,20},{3,0},{3,5},{3,6},{3,17},{3,22},{3,11},{3,21},{7,18},{7,9},{7,19},{7,5},{7,17},{7,11},{7,15},{7,21},{18,9},{18,2},{18,19},{18,10},{18,13},{18,0},{18,5},{18,6},{18,17},{18,11},{9,19},{9,10},{9,20},{9,13},{9,5},{9,6},{9,11},{9,15},{9,21},{2,10},{2,20},{2,5},{2,22},{2,21},{19,10},{19,20},{19,13},{19,17},{19,22},{19,11},{19,15},{19,21},{10,20},{10,13},{10,5},{10,17},{10,22},{10,11},{10,15},{20,13},{20,0},{20,5},{20,17},{20,22},{20,11},{20,15},{13,5},{13,6},{13,17},{13,11},{13,21},{0,6},{0,17},{0,22},{0,15},{0,21},{5,6},{5,15},{5,21},{6,17},{6,22},{6,11},{6,15},{6,21},{17,22},{17,11},{22,15},{22,21},{11,21},{15,21}};
//        int[][] queries = {{17,16},{19,5},{22,10},{6,15},{19,23},{11,10},{1,11},{21,22},{3,9},{20,4},{12,16},{10,8},{15,16},{11,6},{23,18},{23,17},{23,22},{5,19},{10,21},{4,1},{21,12},{7,12},{15,5},{0,19},{14,15},{19,11},{20,10},{12,11},{10,3},{16,15},{3,22},{19,21},{14,17},{16,9},{14,20},{22,23},{21,22},{21,18},{2,19},{20,23},{16,10},{22,20},{6,23},{15,2},{18,19},{19,10},{9,21},{22,21},{21,18},{12,7},{12,22},{19,20},{13,22},{23,22},{16,6},{1,8},{10,2},{15,14},{17,9},{5,8},{2,16},{11,21},{22,23},{6,13},{9,18},{20,22},{1,7},{7,1},{18,20},{21,22},{6,0},{1,9},{18,20},{9,20},{11,6},{23,19},{1,21},{11,17},{20,19},{2,16},{11,22},{13,6},{15,10},{4,1},{22,21},{12,15},{23,18},{16,9},{21,19},{18,20},{11,13},{20,8},{1,9},{14,11},{8,11},{5,6},{22,19},{20,18},{22,21},{21,17},{8,20},{21,20},{8,4},{19,17},{21,10},{21,11},{15,13},{20,11},{0,23},{5,21},{23,22},{1,3},{15,20},{21,22},{5,16},{21,19},{20,23},{23,20},{18,16},{11,15},{1,5},{5,23},{7,12},{10,8},{20,22},{4,1},{13,20},{7,9},{9,7},{9,18},{18,2},{4,10},{12,3},{23,20},{22,23},{19,23},{15,1},{22,10},{16,23},{6,15},{23,22},{17,19},{9,10},{15,18},{13,16},{17,16},{21,14},{9,7},{15,19},{22,2},{12,23},{18,22},{11,19},{13,3},{22,23},{15,8},{7,15},{21,5},{21,8},{3,9},{14,20},{7,20},{12,14},{22,17},{18,17},{17,7},{9,13},{2,11},{22,19},{10,2},{5,23},{19,21},{4,19},{23,19},{14,16},{17,0},{11,15},{19,17},{17,23},{15,8},{16,21},{17,23},{22,12},{8,7},{12,8},{21,18},{19,8},{15,7},{20,16},{19,9},{21,23},{14,20},{5,7},{23,21},{18,21},{11,2},{23,18},{22,23},{2,22},{19,0},{23,19},{23,22},{7,23},{18,23},{5,18},{23,21},{9,6},{20,18},{17,6},{21,23},{23,19},{22,19},{8,7},{20,15},{3,19},{22,21},{13,7},{21,19},{20,21},{15,17},{21,5},{15,21},{18,21},{12,19},{12,23},{14,23},{17,22},{23,22},{21,20},{23,15},{10,14},{18,22},{16,0},{23,22},{7,1},{7,20},{9,23},{18,21},{23,7},{3,10},{14,15},{7,19},{14,12},{15,20},{9,18},{6,4},{11,9},{6,4},{6,18},{19,15},{14,17},{7,10},{21,2},{18,22},{9,15},{8,16},{15,20},{5,9},{2,17},{6,19},{21,15},{12,18},{18,11},{17,12},{21,15},{11,20},{12,22},{23,22},{23,17},{0,5},{22,1},{19,4},{13,15},{20,2},{18,9},{20,6},{3,17},{19,23},{12,2},{14,21},{13,23},{15,2},{21,3},{10,13},{22,13},{19,23},{4,1},{10,6},{0,23},{4,17},{19,12},{21,14},{12,21},{21,23},{14,18},{9,6},{4,3},{11,14},{16,17},{13,19},{14,19},{17,1},{16,15},{19,21},{9,18},{13,14},{11,15},{20,22},{8,15},{17,22},{21,20},{19,23},{21,20},{19,23},{12,6},{18,1},{14,17},{14,18},{15,23},{19,9},{6,2},{15,13},{7,8},{11,8}};


        long l = System.currentTimeMillis();
        List<Boolean> booleans = test.checkIfPrerequisite(k, arr, queries);
        System.out.println(System.currentTimeMillis() - l);
        System.out.println(booleans);
    }

    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        int len = queries.length;
        List<Boolean> list = new ArrayList<>(len);
        if (prerequisites.length == 0 || prerequisites[0].length == 0) {
            for (int i = 0; i < len; i++) {
                list.add(false);
            }
            return list;
        }
        Map<Integer, List<Integer>> all = new HashMap<>();

        for (int[] arr : prerequisites) {
            List<Integer> item = all.computeIfAbsent(arr[0], k -> new ArrayList<>());
            all.computeIfAbsent(arr[1], k -> new ArrayList<>());
            item.add(arr[1]);
        }
        for (int[] query : queries) {
            if (all.get(query[0]) == null || all.get(query[1]) == null) {
                list.add(false);
            } else {
                list.add(find(all, query[0], query[1], new HashMap<>()));
            }
        }
        return list;
    }

    private boolean find (Map<Integer, List<Integer>> all, int st, int end, Map<Integer, Integer> map) {
        List<Integer> list = all.get(st);
        if (list == null) {
            return false;
        }
        for (Integer value : list) {
            if (value == end) {
                return true;
            }
            if (map.get(value) == null) {
                map.put(value, 1);
            } else {
                continue;
            }
            if (find(all, value, end, map)) {
                return true;
            }
        }
        return false;
    }

}
